package 中等.数学;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分
 * 母小于等于  n 的 最简 分数 。分数可以以 任意 顺序返回。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/simplified-fractions/
 */
public class 最简分数_1447 {

    private int[] partPrimeNumber = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

    public static void main(String[] args) {

        System.out.println(new 最简分数_1447().simplifiedFractions(6));
        for (int i = 2; i < 100; i++) {
            if (new 最简分数_1447().isPrimeNumber(i)) {
                System.out.println(i);
            }
        }

    }

    /**
     * 依据题目n的范围
     * 1<=n<=100
     * 所有合数都是由质数的倍数组成
     * 如果分子分母都为质数，那么是最简分数
     * 如果分子分母存在合数，那么如果分子分母可以同时除以某一个质数而没有余数，那么该分数不是最简分数
     *
     * @param n
     * @return
     */
    public List<String> simplifiedFractions(int n) {
        List<String> list = new ArrayList<>();
        while (n > 0) {
            if (n == 1) {
                return list;
            }
            list.add(1 + "/" + n);
            for (int i = 2; i < n; i++) {
                boolean flag = true;
                for (int prime : partPrimeNumber) {
                    if (prime <= i && n % prime == 0 && i % prime == 0) {  //如果能同时除以某个质数，那么排除
                        flag = false;
                        break;
                    }
                }
                if (flag) list.add(i + "/" + n);
            }
            n--;
        }
        return list;
    }

    /**
     * 求质数，遍历到一半大小，如果因数大于一半，一定不是质数
     * 因为num/(num/2+1)<2
     *
     * @param num
     * @return
     */
    public boolean isPrimeNumber(int num) {
        for (int i = 2; i <= num / 2; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

}
